#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIM 17000      //para o tamanho dos vetores
#define LIM2 100    //para o tamanho das strings
#define LIM3 200
#define NUM 65535     //usado na funcao hash
#define NULO 0
#define DELETED -1
#define PDELETED ((Dados*)-1)

struct dados {    //vetor dos IDs, onde serao armazenados os dados
  int id;
  char fn[LIM2];   //first name
  char ln[LIM2];   //last name
  char bd[LIM2];   //birthday
  char pn[LIM2];   //phone number
  struct dados **pfn, **pln, **pbd, **ppn;
}typedef Dados;

Dados *query_aux[LIM3];

inline unsigned int hash(char *string) {  //rever
  register unsigned int x = 0;
  register unsigned int *p = (unsigned int*)string;
  while(*p != 0){
    x = ((x<<1)^(*p++))%NUM;
  }
  return x;
}

inline int skip(int i) { //rever
  return i*13;
}

void print_erro(int id, int erro) {
  printf(erro == 1 ? "ID %d nao existente.\n" : "ID %d ja cadastrado.\n", id);
}

Dados **insere_vetor(Dados *p, char *string, Dados **vetor, Dados *dt){ //insere a string (fn, ln, bd ou pn) no respectivo vetor
  unsigned int i, x = (hash(string))%LIM;
  for(i = 1; ; i++){
    if(vetor[x] == NULL || vetor[x] == PDELETED){   //lugar livre encontrado
      vetor[x] = p;
      break;
    }
    x = (x+skip(i))%LIM;
  }
  return &(vetor[x]);
}

void info(int id, Dados *dt) {    //imprime as informacoes, dado um ID
  int i;
  Dados *p = dt + (id%LIM);
  for(i = 1; ; i++) {
    if(p->id != NULO) {   //nao esta livre
      if(p->id == id) {   //id encontrado
        printf("%s %s %s %s\n", p->fn, p->ln, p->bd, p->pn);
        break;
      }
      else {   //colisao: fazer skip
        p = dt + (id+skip(i))%LIM;
      }
    }
    else {    //id nao existe
      print_erro(id, 1);
      break;
    }
  }
}

void deleta(int id, Dados **fn, Dados **ln, Dados **bd, Dados **pn, Dados *dt) { // deleta uma informacao, dado um id
  int i;
  Dados *p = dt + (id%LIM);
  for(i = 1; ; i++) {
    if(p->id != NULO) {
      if(p->id == id) {   //id encontrado: deletar
        *(p->pfn) = *(p->pln) = *(p->pbd) = *(p->ppn) = PDELETED;
        memset(p, 0, sizeof(Dados));
        p->id = DELETED;
        break;
      }
      else {   //colisao: fazer skip
        p = dt + (id+skip(i))%LIM;
      }
    }
    else {
      print_erro(id, 1);
      break;
    }
  }
}

int cmp(const void *p1, const void *p2)
{
  return (*(Dados**)p1)->id - (*(Dados**)p2)->id;
}

Dados **search1(char *s, Dados **v, int tipo, int *nel)
{
  Dados **b;
  Dados **a2 = query_aux;
  char *s2;
  unsigned int i, x = hash(s)%LIM;
  b = v + x;
  for(i = 1; ; i++)
  {
    if(*b == NULL) break;
    if(*b != PDELETED)
    {
      switch(tipo)
      {
        case 1: //fn
          s2 = (*b)->fn;
          break;
        case 2:
          s2 = (*b)->ln;
          break;
        case 3:
          s2 = (*b)->bd;
          break;
        case 4:
          s2 = (*b)->pn;
          break;
      }
      if(strcmp(s,s2)==0) *a2++ = *b;
    }
    x = (x+skip(i))%LIM;
    b = v + x;
  }
  *a2 = NULL;
  *nel = a2-query_aux;
  return query_aux;
}

Dados **search2(char *s, Dados **v, int tipo, int *nel)
{
  Dados **b;
  Dados **a2 = query_aux;
  char *s2;
  b = v;
  while(1)
  {
    if(*b == NULL) break;
    switch(tipo)
    {
      case 1: //fn
        s2 = (*b)->fn;
        break;
      case 2:
        s2 = (*b)->ln;
        break;
      case 3:
        s2 = (*b)->bd;
        break;
      case 4:
        s2 = (*b)->pn;
        break;
    }
    if(strcmp(s,s2)==0) *a2++ = *b;
    b++;
  }
  *a2 = NULL;
  *nel = a2-query_aux;
  return query_aux;
}

void query(Dados **fn, Dados **ln, Dados **bd, Dados **pn, Dados *dt)
{
  int i = 1, nel;
  Dados **proc, **proc2;
  char input[LIM2], c;

  memset(input, 0, LIM2);
  scanf("%s", input);
  if(strstr(input, "fn:") != NULL)
  {
    proc = search1(input+3, fn, 1, &nel);
  }
  else
  if(strstr(input, "ln:") != NULL)
  {
    proc = search1(input+3, ln, 2, &nel);
  }
  else
  if(strstr(input, "bd:") != NULL)
  {
    proc = search1(input+3, bd, 3, &nel);
  }
  else
  if(strstr(input, "pn:") != NULL)
  {
    proc = search1(input+3, pn, 4, &nel);
  }
  if(*proc == NULL)
  {
    printf("\n");
    return;
  }
  while(1)
  {
    c = getc(stdin);
    if(c == '\n') break;  //para o query
    else ungetc(c, stdin);

    memset(input, 0, LIM2);
    scanf("%s", input);
    if(strstr(input, "fn:") != NULL)
    {
      proc = search2(input+3, proc, 1, &nel);
    }
    else
    if(strstr(input, "ln:") != NULL)
    {
      proc = search2(input+3, proc, 2, &nel);
    }
    else
    if(strstr(input, "bd:") != NULL)
    {
      proc = search2(input+3, proc, 3, &nel);
    }
    else
    if(strstr(input, "pn:") != NULL)
    {
      proc = search2(input+3, proc, 4, &nel);
    }
  }
  if(nel == 0)
  {
    printf("\n");
    return;
  }
  qsort(proc, nel, sizeof(Dados*), cmp);
  for(proc2 = proc ; *proc2 != NULL; proc2++)
  {
    if(i)
    {
      printf("%d", (*proc2)->id);
      i = 0;
    }
    else printf(" %d", (*proc2)->id);
  }
  printf("\n");
}

void ler_telefone(char *s)
{
  char c;
  c = getc(stdin);
  while(1)
  {
    c = getc(stdin);
    if((c >= 'a' && c <= 'z') || c == '\n' || c == ' ')
    {
      ungetc(c, stdin);
      break;
    }
    *s++ = c;
  }
  *s = '\0';
}

int main(void) {
  int id, i;
  char input[LIM2];
  Dados **vetor_first_name, **vetor_last_name, **vetor_birthday, **vetor_phone_number;
  memset(input, 0, LIM2);
  Dados *vetor_dados;
  vetor_first_name = (Dados**)calloc(LIM, sizeof(Dados*));
  vetor_last_name = (Dados**)calloc(LIM, sizeof(Dados*));
  vetor_birthday = (Dados**)calloc(LIM, sizeof(Dados*));
  vetor_phone_number = (Dados**)calloc(LIM, sizeof(Dados*));
  vetor_dados = (Dados*)calloc(LIM, sizeof(Dados));

  while(scanf("%s", input) != EOF) {
    if(strcmp(input, "add") == 0){   //adiciona um novo individuo
      scanf("%d", &id);
      Dados *p = vetor_dados + (id%LIM);
      for(i = 1; ; i++) {  //verificando se o id ja existe
        if(p->id > 0) {   //nao esta livre
          if(p->id == id) {   //id ja existe
            print_erro(id, 0);
            break;
          }
          else {   //colisao: fazer skip
            p = vetor_dados + (id+skip(i))%LIM;
          }
        }
        else {   //id esta livre: inserir
          p->id = id;
          scanf("%s %s %s", p->fn, p->ln, p->bd); //lendo
          ler_telefone(p->pn);

          p->pfn = insere_vetor(p, p->fn, vetor_first_name, vetor_dados);
          p->pln = insere_vetor(p, p->ln, vetor_last_name, vetor_dados);
          p->pbd = insere_vetor(p, p->bd, vetor_birthday, vetor_dados);
          p->ppn = insere_vetor(p, p->pn, vetor_phone_number, vetor_dados);
          break;
        }
      }
    }

    if(strcmp(input, "del") == 0) {
      scanf("%d", &id);
      deleta(id, vetor_first_name, vetor_last_name, vetor_birthday, vetor_phone_number, vetor_dados);
    }

    if(strcmp(input, "info") == 0) {
      scanf("%d", &id);
      info(id, vetor_dados);
    }

    if(strcmp(input, "query") == 0) {
      query(vetor_first_name, vetor_last_name, vetor_birthday, vetor_phone_number, vetor_dados);
    }
  }

                              //liberando a memoria alocada
  free(vetor_dados);          //
  free(vetor_first_name);     //
  free(vetor_last_name);      //
  free(vetor_birthday);       //
  free(vetor_phone_number);   //

  return 0;
}
